package com.xinwei.leetcode.数组;

import java.util.HashMap;

// https://leetcode-cn.com/problems/majority-element/
public class _169_多数元素 {
    // 哈希表
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                Integer integer = hashMap.get(nums[i]);
                if (integer >= nums.length / 2) return nums[i];
                hashMap.replace(nums[i], integer + 1);
            } else {
                hashMap.put(nums[i], 1);
            }
        }
        return nums[0];
    }

    //方法二：排序

    //方法三：随机化

    //方法四：分治
}
